#include "SList.h"

void SListPrint(SListNode *phead)
{
    //链表一开始为空，无need判断
    SListNode *cur = phead;
    while (cur != NULL)
    {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

SListNode *BuySListNode(SLTDataType x)
{
    SListNode *newNode = (SListNode *)malloc(sizeof(SListNode));
    if (newNode == NULL)
    {
        printf("malloc fail!!!\n");
        exit(EXIT_FAILURE);
    }
    else
    {
        newNode->data = x;
        newNode->next = NULL;
    }
    return newNode;
}

void SListPushBack(SListNode **pphead, SLTDataType x)
{
    //判断二级指针是否为空
    assert(pphead);
    //创建新节点
    SListNode *newNode = BuySListNode(x);
    //节点为空时直接链接
    if (*pphead == NULL)
    {
        *pphead = newNode;
    }
    else
    {
        //不为空时：找尾->链接
        SListNode *tail = *pphead;
        while (tail->next != NULL)
        {
            tail = tail->next;
        }
        //链接
        tail->next = newNode;
    }
}

void SListPushFront(SListNode **pphead, SLTDataType x)
{
    //判断二指针是否为空
    assert(pphead);
    SListNode *newNode = BuySListNode(x);
    if (*pphead == NULL)
    {
        *pphead = newNode;
    }
    else
    {
        newNode->next = *pphead;
        *pphead = newNode;
    }
}

void SListPopBack(SListNode **pphead)
{
    assert(pphead);
    //如果节点为空，那么不需要删除
    if (*pphead == NULL)
    {
        return;
    }
    else if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        SListNode *tail = *pphead;
        SListNode *prev = NULL;
        //找尾上一个节点
        while (tail->next != NULL)
        {
            prev = tail;
            tail = tail->next;
        }
        free(tail);
        prev->next = NULL;
    }
}

void SListPopFront(SListNode **pphead)
{
    assert(pphead);
    if (*pphead == NULL)
    {
        return;
    }
    else
    {
        SListNode *next = (*pphead)->next;
        free(*pphead);
        *pphead = next;
    }
}

SListNode *SListFind(SListNode *phead, SLTDataType x)
{
    SListNode *cur = phead;
    while (cur != NULL)
    {
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

void SListInsert(SListNode **pphead, SListNode *pos, SLTDataType x)
{
    assert(pphead);
    assert(pos);
    SListNode *newNode = BuySListNode(x);
    if (*pphead == NULL)
    {
        return;
    }
    else if ((*pphead)->next == pos)
    {
        SListPushFront(pphead, x);
    }
    else
    {
        SListNode *prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
        }
        newNode->next = pos;
        prev->next = newNode;
    }
}

void SListErase(SListNode **pphead, SListNode *pos)
{
    assert(pphead);
    assert(pos);
    //节点为空即不用删除
    if (*pphead == NULL)
    {
        return;
    }
    else
    {
        SListNode *prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
        }
        prev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

void SListInsertAfter(SListNode **pphead, SListNode *pos, SLTDataType x)
{
    assert(pphead);
    assert(pos);
    if (*pphead == NULL)
    {
        return;
    }
    else
    {
        SListNode *newNode = BuySListNode(x);
        newNode->next = pos->next;
        pos->next = newNode;
    }
}

void SListEraseAfter(SListNode **pphead, SListNode *pos)
{
    assert(pphead);
    assert(pos);
    if (pos->next == NULL)
    {
        return;
    }
    else
    {
        SListNode *next = pos->next;
        if (next)
        {
            pos->next = next->next;
            free(next);
            next = NULL;
        }
    }
}

void SListDestory(SListNode **pphead)
{
    assert(pphead);
    SListNode *cur = *pphead;
    while (cur != NULL)
    {
        //保存上一个节点地址
        SListNode *next = cur->next;
        free(cur);
        cur = next;
    }
    *pphead = NULL;
}

int main()
{
    //尾插
    SListNode *sl = NULL;
    SListPushBack(&sl, 1);
    SListPushBack(&sl, 2);
    SListPushBack(&sl, 3);
    SListPushBack(&sl, 4);
    SListPushBack(&sl, 5);
    SListPrint(sl);

    //头插
    SListPushFront(&sl, 0);
    SListPushFront(&sl, -1);
    SListPushFront(&sl, -2);
    SListPrint(sl);

    //尾删
    SListPopBack(&sl);
    SListPopBack(&sl);
    SListPrint(sl);

    //头删
    SListPopFront(&sl);
    SListPopFront(&sl);
    SListPopFront(&sl);
    SListPrint(sl);

    //查找
    SListNode *pos = SListFind(sl, 3);
    if (pos == NULL)
    {
        printf("没找到...\n");
    }
    else
    {
        printf("找到了: %p\n", pos);
    }

    //随机插入
    SListInsert(&sl, pos, 100);
    SListPrint(sl);

    //随机删除
    SListErase(&sl, pos);
    SListPrint(sl);

    // pos位置后面插入新节点
    SListNode *pos2 = SListFind(sl, 1);
    SListInsertAfter(&sl, pos2, 200);
    SListPrint(sl);

    //删除pos后一位的节点
    SListEraseAfter(&sl, pos2);
    SListPrint(sl);

    //释放链表
    SListDestory(&sl);
    SListPrint(sl);
    system("pause");
    return 0;
}